package heap;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 347. 前 K 个高频元素
 * https://leetcode-cn.com/problems/top-k-frequent-elements/
 */
public class 前K个高频元素 {
    class Pare implements Comparable<Pare>{
        int key ;
        int times;

        public Pare(int key, int times) {
            this.key = key;
            this.times = times;
        }

        @Override
        public int compareTo(Pare o) {
            return this.times - o.times;
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];
        Map<Integer , Integer> map = new HashMap<>();//这里面存了啥，存了出现元素和次数的记录
        Queue<Pare> queue = new PriorityQueue<>();//优先级队列
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
            //分情况把出现的元素和次数存放到map中
//            if (map.containsKey(nums[i])){
//                map.put(nums [i] , map.get(nums[i]) + 1);
//            }else {
//                map.put(nums [i] , 1);
//            }
        }
        /**
         * 看下面这个写法，理解一下为啥这里就要循环map二不是原数组了
         */
//        for (int i = 0; i < nums.length; i++) {
//            if (queue.size() < k){
//                queue.offer(new Pare(nums[i] , ));
//            }
//        }
        //所以直接循环遍历map就行
        for (Map.Entry<Integer , Integer> entry :map.entrySet()//map的foreach，注意Map.Entry<Integer , Integer>引用类型
             ) {
            if (queue.size() < k){
                queue.offer(new Pare(entry.getKey() , entry.getValue()));
            }else {
                Pare curPare = queue.peek();
                if (curPare.times < entry.getValue()){//取频次最高的k个，times最大的k个
                    //所以对吧假如出现次数比顶大（最小堆顶是最小的），就加到堆里
                    queue.poll();
                    queue.offer(new Pare(entry.getKey() , entry.getValue()));

                }else {
                    //比顶还小那就不管它了
                    continue;
                }
            }
        }
        //想想等这个都循环完，堆里就存的是出现次数最多的几个元素，不管map什么事了
        for (int i = 0; i < ret.length; i++) {
            ret[i] = queue.poll().key;
        }
        return ret;
    }
}
